package Q18

import java.util.*
import kotlin.collections.ArrayList

class Main {

}


class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val res: MutableList<List<Int>> = ArrayList()
        Arrays.sort(nums)
        for (i in nums.indices) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue
            }

            //二层循环
            for (j in i + 1 until nums.size) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue
                }
                var left = j + 1
                var right = nums.size - 1
                while (left < right) {
                    val sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if (sum > target) {
                        right--
                    } else if (sum < target) {
                        left++
                    } else {
                        res.add(ArrayList(Arrays.asList(nums[i], nums[j], nums[left], nums[right])))
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--
                        }
                        left++
                        right--
                    }
                }
            }
        }
        return res
    }
}